package com.lql.sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 1, 0};
        int[] ints = new int[8000000];
        Random random = new Random();
        for (int i = 0; i < 8000000; i++) {
            ints[i] = random.nextInt(8000000);
        }
        long startTime = System.currentTimeMillis();
        System.out.println("开始：" + startTime);
        quickSort(ints, 0, 7999999);
        long endTime = System.currentTimeMillis();
        System.out.println("结束：" + endTime);
        float l = (endTime - startTime) / 1000f;
        System.out.println("总时间：" + l + "秒");
    }

    /**
     * 执行快速排序
     *
     * @param arrays 待排序的数组
     * @param start  左索引
     * @param end    右下标索引
     * @return 返回数组
     */
    public static int[] quickSort(int[] arrays, int start, int end) {

        int left = start;
        int right = end;
        //表示中轴值为当前数组的首个元素
        int pivot = arrays[left];
        while (left < right) {
            // 右边寻找小于中轴值的
            while (left < right && pivot <= arrays[right]) {
                right--;
            }
            //左右互换
            arrays[left] = arrays[right];
            //左边寻找大于中轴值的
            while (left < right && pivot >= arrays[left]) {
                left++;
            }
            //左右互换
            arrays[right] = arrays[left];
        }
        arrays[left] = pivot;
        if (left > start) {
            //左递归排序
            arrays = quickSort(arrays, start, left);
        }
        if (left + 1 < end) {
            arrays = quickSort(arrays, left + 1, end);
        }
        return arrays;
    }
}
